public class Test {
    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> list = new ArrayList<>();
            if(root == null) {
                return list;
            }

            Queue<TreeNode> que = new LinkedList<>();
            que.offer(root);

            while( !que.isEmpty()) {

                List<Integer> num = new ArrayList<>();
                int size = que.size();

                while(size != 0) {

                    TreeNode cur = que.poll();
                    num.add(cur.val);

                    if(cur.left != null) {
                        que.offer(cur.left);
                    }
                    if(cur.right != null) {
                        que.offer(cur.right);
                    }
                    size--;
                }
                list.add(num);
            }
            return list;
        }
    }
    class Solution {
        public boolean isSymmetric(TreeNode root) {
            if(root == null) {
                return true;
            }

            return isSymmetrichild(root.left,root.right);
        }

        public boolean isSymmetrichild(TreeNode leftroot,TreeNode rightroot) {
            if(leftroot == null && rightroot != null || leftroot != null && rightroot == null) {
                return false;
            }

            if(leftroot == null && rightroot == null) {
                return true;
            }

            if(leftroot.val != rightroot.val) {
                return false;
            }

            return isSymmetrichild(leftroot.left,rightroot.right) &&
                    isSymmetrichild(leftroot.right,rightroot.left);
        }
    }
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }

        int left = getHight(root.left);
        int right = getHight(root.right);

        return Math.abs(left-right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    public int getHight(TreeNode root) {
        if(root == null) {
            return 0;
        }

        int left = getHight(root.left);
        int right = getHight(root.right);

        return left > right ? left + 1 : right + 1;
    }
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }

        TreeNode num = root.left;
        root.left = root.right;
        root.right = num;

        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null) {
            return false;
        }

        if(isSameTree(root,subRoot)) {
            return true;
        }

        if(isSubtree(root.left,subRoot)) {
            return true;
        }

        if(isSubtree(root.right,subRoot)) {
            return true;
        }

        return false;

    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q != null || q == null && p != null) {
            return false;
        }

        if(p == null && q == null) {
            return true;
        }

        if(p.val != q.val) {
            return false;
        }

        return isSameTree(q.left,p.left) && isSameTree(q.right,p.right);
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q != null || q == null && p != null) {
            return false;
        }

        if(p == null && q == null) {
            return true;
        }

        if(p.val != q.val) {
            return false;
        }

        return isSameTree(q.left,p.left) && isSameTree(q.right,p.right);
    }
}
